package middle;

import util.PrintUtils;

public class Solution_34 {

    public int[] searchRange(int[] nums, int target) {
        int begin = nums.length - 1;
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            if (left + 1 >= right) {
                if (target < nums[left]) {
                    begin = left - 1;
                } else if (target > nums[right]) {
                    begin = right + 1;
                } else if (target == nums[left]) {
                    begin = left;
                } else if (target == nums[right]) {
                    begin = right;
                }
                break;
            }
            int middle = (left + right) >> 1;
            if (nums[middle] >= target) {
                right = middle;
            } else {
                left = middle + 1;
            }
        }

        int end = 0;
        int left1 = 0, right1 = nums.length - 1;
        while (left1 <= right1) {
            if (left1 + 1 >= right1) {
                if (target < nums[left1]) {
                    end = left1 - 1;
                } else if (target > nums[right1]) {
                    end = right1 + 1;
                } else if (target == nums[right1]) {
                    end = right1;
                } else if (target == nums[left1]) {
                    end = left1;
                }
                break;
            }
            int middle = (left1 + right1) >> 1;
            if (nums[middle] <= target) {
                left1 = middle;
            } else {
                right1 = middle - 1;
            }
        }

        if (begin <= end && begin >= 0 && end < nums.length && nums[begin]==target && nums[end]==target) {
            return new int[]{begin, end};
        } else {
            return new int[]{-1, -1};
        }
    }

    public static void main(String[] args) {
        Solution_34 model = new Solution_34();
        PrintUtils.arrayInt(model.searchRange(new int[]{1,1,1,2,2,3,3,3,4,5,5,5,5,6,6,6,6,9,9,9},7));
        PrintUtils.arrayInt(model.searchRange(new int[]{}, 1));
        PrintUtils.arrayInt(model.searchRange(new int[]{-1, 4, 5, 6}, 1));
        PrintUtils.arrayInt(model.searchRange(new int[]{-1, 4, 5, 6}, -5));
        PrintUtils.arrayInt(model.searchRange(new int[]{-1, 4, 5, 6}, 7));
        PrintUtils.arrayInt(model.searchRange(new int[]{-1, 4, 5, 6}, 4));
        PrintUtils.arrayInt(model.searchRange(new int[]{-1, 4, 5, 6}, 5));
        PrintUtils.arrayInt(model.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8));
        PrintUtils.arrayInt(model.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 6));
    }
}
